import java.util.Random;
    //力扣 912 排序数组
public class test1 {

    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;
    }

    //快速排序，把数组分成三份
    public void qsort(int[] nums,int l,int r){
        //递归出口
        if(l>=r){
            return;
        }
        Random random = new Random();
        //获取随机值
        int key = nums[random.nextInt(r-l+1)+l];
        //初始化left和right以及i指针
        int left = l-1,right = r+1,i = l;
        //这里和上一题的颜色分类一样，用数组分三块的思想，实现快排
        while(i<right){
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else{
                swap(nums,--right,i);
            }
        }
        //继续调用继续排序左右两边的数组
        qsort(nums,l,left);
        qsort(nums,right,r);
    }

    public void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
